package LeetCode刷题.暑假刷的算法;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-08-15 09:35
 * @description: Functions of this class is 找出二叉树的路径最大值
 **/
public class 二叉树的路径最大值 {
    public static class TNode {
        int val;
        TNode left, right;
    }

    private static TNode createTree(int nums[], int start, int end) {
        TNode T = null;
        if (start <= end) {
            int mid = (start + end + 1) >> 1;
            T = new TNode();
            T.val = nums[mid];
            T.left = createTree(nums, start, mid - 1);
            T.right = createTree(nums, mid + 1, end);
        }
        return T;
    }

    private static int tempMax = Integer.MIN_VALUE;

    public static int findPath(TNode T) {
        if (T != null) {
            //递归找出左右子树中路径最大值
            int sumLeft = findPath(T.left);//以左子树为起始点的最大路径和
            int sumRight = findPath(T.right);//以右子树为起始点的最大路径和

            int allMax = sumRight + sumLeft + T.val;//左右子树都算上的一条路径
            int leftMax = sumLeft + T.val;//只算左边的那条子树路径最大
            int rightMax = sumRight + T.val;//只算右边的那条子树路径最大

            int MaxPath = Math.max(Math.max(leftMax, rightMax), allMax);//然后找出三者中的最大值
            if (MaxPath > tempMax) {//通过一个临时节点用于替换
                tempMax = MaxPath;
            }
            //然后就要找出左子树和右子树哪边最大，然后返回最大的子树
            int sumMax = sumLeft >= sumRight ? sumLeft : sumRight;
            return sumMax + T.val;
        }
        return 0;
    }

    public static void main(String args[]) {
        int nums[] = {1, 2, 3, 4, 5, 6, 7};
        TNode T = createTree(nums, 0, nums.length - 1);
        findPath(T);
        System.out.println("二叉树中的路径最大值为：" + tempMax);
    }
}